package euler.p051_100;

import java.math.BigInteger;

import euler.MainEuler;
import euler.helper.NaturalHelper;

public class Euler053 extends MainEuler {

    /*
        There are exactly ten ways of selecting three from five, 12345:

        123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

        In combinatorics, we use the notation, 5C3 = 10.

        In general,
        nCr = n!/(r!*(n−r)!)
            ,where r ≤ n, n! = n×(n−1)×...×3×2×1, and 0! = 1.

        It is not until n = 23, that a value exceeds one-million:
        23C10 = 1144066.

        How many, not necessarily distinct, values of  nCr, for
        1 ≤ n ≤ 100, are greater than one-million?

     */
    public String resolve() {

        int limite = 1000000;

        int count = 0;

        for (int i = 1; i <= 100; i++) {
            for (int j = 0; j <= i/2; j++) {
                BigInteger comb = combinatoria(i, j);
                if (comb.intValue() > limite) {
                    for(;j <= i/2; j++) {
                        if (2*j == i){
                            count++;
                        } else {
                            count+=2;
                        }
                    }
                }
            }
        }

        return String.valueOf(count);
        // 4075
    }

    private static BigInteger combinatoria(int n, int r) {
        return NaturalHelper.bigFactorial(n).divide(NaturalHelper.bigFactorial(r).multiply(NaturalHelper.bigFactorial(n-r)));
    }
}
